import java.util.ArrayList;


public class NearestNeigbour {
	ArrayList <Integer> visited = new ArrayList<Integer>();
	int currentNode = 0;
	
	public ArrayList <Integer> solve(double [][] array,int x, int y){
		return getPath(array ,x,y);
		
	}
	
	private ArrayList <Integer> getPath(double [][]array, int x, int y){
		
		int cost = 0;
		
		visited.clear();
		visited.add(0);
		currentNode = 0;
		
		while(visited.size()<x){
			double min = -1;
			int cityMin = 0;
			for(int j = 0; j< y; j++){
				if(visited.indexOf(j)== -1){
					if(min<0 || min>array[currentNode][j]){
						min = array[currentNode][j];
						cityMin = j;
					} 
				}
			}
			cost+=min;
			visited.add(cityMin);
			currentNode = cityMin;
			
		}
		
		System.out.println("Cost =" + cost);	
		System.out.println("Path =" + listToArray());
		return visited;
		
	}
	private String listToArray(){
		String str = "";
		
		for(int i = 0; i < visited.size(); i++){
			
			str+=visited.get(i)+" ";
		}
		return str;
		
	}
	
	
}
